You are in a crowd of $n$ people; over half of them belong to the same secret party.
You go around asking questions; the only question you can ask is ``are these two
people (pointing at one, then at another) from the same party?'' Everyone in the
crowd is truthful.

Use a divide-and-conquer approach to identify with no possibility of error one
person who belongs to the secret party. (Note that it is possible to solve this
problem in linear time by other techniques; the divide-and-conquer algorithm
will impose an extra factor of log $n$, but it is what is asked of you here.)
\\\\
We will start by showing some claims about the problem. Without loss of generality we assume $n$ is an even number. Let a person belonging to the secret group denoted as $S$.

\begin{claim}
If we randomly combine the $n$ people into couples, then at least one couple will consist of two $S$s.
\label{claim:couples}
\end{claim}
\begin{proof}
Since there are more than $\frac{n}{2}$ $S$s, even if we spread the $n/2$ $S$s into the $n$ groups, there will be at least a remaining $S$ that has to be paired with an $S$.
\end{proof}

\begin{claim}
If we randomly combine the $n$ people into couples, then the number of couples consisting of two $S$s will be larger than the number of couples consisting of two people of a single other group.
\label{claim:other-group}
\end{claim}
\begin{proof}
Claim \ref{claim:couples} says that the minimum number of couples consisting of two $S$s is one. This ``worst-case'' happens only when $|S| = \frac{n}{2} + 1$ and each couple contains at least one $S$. 

Assume now that there is another group $X$ and an allocation of couples s.t. the number of couples consisting of two $X$s is larger than the number of couples consisting of two $S$s. Assume the number of couples of $X$s is $x$. Due to the aforementioned, for every pair of $X$s, we have a ``spair'' $S$ that will be coupled with another $S$, since in the ``worst-case'' we had that every couple contains an $S$. Therefore, if we have $x$ pairs of $X$s, we also create $x$ ``new'' pairs of $S$s. Hence, $x$ pairs of $S$s, plus the one that we proved that always exists, make $x+1$ pairs of $S$s; a contradiction.
\end{proof}

\begin{claim}
If we randomly combine the $n$ people into couples, then the number of couples consisting of two $S$s will be larger than the total number of couples consisting of two people from the same group (any group).
\end{claim}
\begin{proof}
The proof of claim \ref{claim:other-group} applies as is for this claim too.
\end{proof}

We apply the exact same idea as in mergesort algorithm to solve the problem. We use divide and conquer with recursive calls to the same function until we break the problem down to individuals. Afterwards, we merge the results of the recursive calls. Our algorithm represents the results as tuples, i.e. when returning for an individual $Y$, the returned value is $\{Y, 1\}$, which indicates that we have a single person that belongs to the same group as $Y$. So, $\{Y, 2\}$ indicates that we have found 2 people that belong to the same group as $Y$.

Our algorithm will keep at which node two largest discovered parties in the whole subtree. In the end based on the results in the root the person in which group the number of people will be the largest will be returned. In case when both returned groups contains the same number of people, we suggest to randomly reorder the people, which didn't have pair on the bottom level.

So the algorithm for finding two best parties is the following:
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
	large_Group_S(People) {
		if (|People| = 1) { /*individual*/
			Person = get_elem(People)
			return {Person, 1};
		}
		else {
			{Left, Right} = split_middle(People);/*|Left| = |Right|*/
			return merge_S(	large_Group_S(Left), large_Group_S(Right));
		}
	}
	\end{lstlisting}

\begin{figure}[h]
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
	merge_S(Left, Right) {
		if (Left is empty) {
			return Right;
		}
		else if {Right is empty) {
			return Left;
		}
		else { /*none empty*/
			/*merge the results, keeping all the found couples. For example, [{S,2}, {X,2}] with [{Y,2}, {S,2}] gives: [{S,4}, {X,2}, {Y,2}]*/
			Res = [];
			for (each {L, Ln} in Left) {
				for (each {R, Rn} in Right) {
					if (same_group(L,R)) {
						add({L, Ln + Rn}, Res);	
						delete({L,Ln}, Left);
						delete({R,Rn}, Right);				
					}
				}			
			}
			add(Left, Res);	
			add(Right, Res);
			return Res;
		}
	}
	\end{lstlisting}
\end{figure}

Our algorithm takes advantage of the 3 claims we proved earlier. We know that at the lower level of the recursion, when merging independent people, the number of couples of $S$s that will be created will be more than any other group and actually greater than the number of couples with both people from the same group of any group. Therefore, since the algorithm forwards and merges all the couples found on the lower level upwards, in the root the person which has the highest number belongs the secret group.

As for the running time of the algorithm, it can be calculated by the recurrence $T(n) = 2T(n/2) + O(n^2)$, since at every step, we merge the two lists using the for loops. Therefore our algorithm is $O(n^2)$, as it can be easily found by the Master Theorem.